1. Field of the Invention
This invention relates to content addressable memories and, more particularly, to a circuit for detecting multiple matches in a content addressable memory.
2. Description of the Related Art
Content addressable memories (CAMs) compare a search word with a set of stored words. An indication of whether or not the search word matches the stored words is produced for each stored word. A distinguishing characteristic of a CAM is that each stored word is uniquely identified on the basis of the content of the word itself, rather than by its address within the memory array as in conventional digital memories.
A CAM includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information. The bits stored in a row of memory elements constitute a stored word. During a match operation, a search word of input data is applied to all the rows, and an indication is produced for each row as to whether or not the search word matches the word stored therein.
One possible use for a CAM is to facilitate searches on a conventional indexed random access memory (RAM). The CAM stores a series of "tags" which represent address locations in the RAM. Match operations are performed on the CAM in order to find the locations of data stored in the RAM. When match data is presented to the CAM, the CAM responds with a "tag" representing the address location in RAM containing the desired data. This address location can then be fed to the RAM's address lines in order to access the data.
A problem may occur when there is a "multiple match", i.e. more than one row of the CAM tries to indicate a match with the match data. If the CAM lines are connected directly to the RAM's address lines, then a multiple match will cause more than one RAM address line to be asserted simultaneously. Some RAMs are incapable of responding properly when more than one line is asserted simultaneously. In addition, assertion of multiple address lines may even be destructive for some RAMs.
Consequently, when a CAM is to be used with a conventional RAM that is not suited to receive multiple matches, it is imperative that the RAM never see more than one asserted address line. It is also useful for the system to be alerted to the fact that a multiple match has occurred, so that appropriate action may be taken (such as treating the stored data as invalid, or rechecking the CAM contents).